package LeetCodeHot100TopInterview;

import java.util.*;

public class Q015_TreeNumSum {
    //两数之和延伸 三数之和 a + b + c == 0 ?
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length == 0){
            return new ArrayList<>();
        }
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            //去重  这种线性去重要么使用 Hashset
            //要么就排序然后前后指针  其实就是时空的一个取舍
            if (i == 0  || nums[i] != nums[i - 1]){
                List<List<Integer>> ret = twoSum(nums, -nums[i], i + 1, nums.length - 1);
                for (List<Integer> list : ret) {
                    list.add(nums[i]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }

    //两数之和 由于调用次数过多 每次都需要一个 线性空间复杂度 故全流程做一次排序 省空间
    public List<List<Integer>> twoSum(int[] nums, int target, int begin, int end) {
        //num - index
//        Map<Integer,Integer> map = new HashMap<>();
        //
        List<List<Integer>> ans = new ArrayList<>();
        int left = begin;
        int right = end;
        while (left < right){
            if (nums[left] + nums[right] == target){
                if (left == 0 || nums[left] != nums[left - 1]){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[left]);
                    list.add(nums[right]);
                    ans.add(list);
              }
                //提出来
                left ++;

            }else if (nums[left] + nums[right] < target){
                left++;
            }else {
                right--;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Q015_TreeNumSum fun = new Q015_TreeNumSum();
        System.out.println(fun.threeSum(new int[]{-2, 0, 0, 2, 2}));
    }
}
